package com.leetcode.sorts.tree;

/**
 * @Author: WuPeng
 * @Date: 2021/6/8 2:11 下午
 *
 * 112.路径总和
 *
 * 给你二叉树的根节点root 和一个表示目标和的整数targetSum ，
 * 判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有
 * 节点值相加等于目标和targetSum 。
 *
 * 叶子节点 是指没有子节点的节点。
 *
 */
public class PathSum_112 {

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        return getSum(root, targetSum-root.val);
    }

    private boolean getSum(TreeNode node, int sum) {

        if (node.left == null && node.right == null && sum == 0) return true;
        if (node.left == null && node.right == null) return false;

        if (node.left != null){
            sum -= node.left.val;
            if (getSum(node.left, sum)) return true;
            sum += node.left.val; //回溯，撤销处理结果
        }

        if (node.right != null){
            sum -= node.right.val;
            if (getSum(node.right, sum)) return true;
            sum += node.right.val; //回溯，撤销处理结果
        }
        return false;
    }

}
